package answer_1_10

import "fmt"

//给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
//
//示例 1:
//输入: s = "abcabcbb"
//输出: 3
//解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

//示例 2:
//输入: s = "bbbbb"
//输出: 1
//解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

//示例 3:
//输入: s = "pwwkew"
//输出: 3
//解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
//     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

//提示：
//0 <= s.length <= 5 * 104
//s 由英文字母、数字、符号和空格组成

func Answer_3() {
	fmt.Println(lengthOfLongestSubstring_1("abcabcbb"))
}

func lengthOfLongestSubstring_1(s string) int {
	n := len(s)
	if n <= 1 {
		return n
	}
	m := map[byte]int{}
	left := 0
	right := 0
	maxLen := 0
	for right < n {
		if _, ok := m[s[right]]; !ok {
			m[s[right]] = right
		} else {
			if m[s[right]]+1 >= left {
				left = m[s[right]] + 1
			}
			m[s[right]] = right
		}
		maxLen = max(right-left+1, maxLen)
		right++
	}
	return maxLen
}

func lengthOfLongestSubstring_2(s string) int {
	n := len(s) // 获得字符串长度
	if n <= 1 { // 对于字符串长度为0,1的可以直接返回了
		return n
	}

	// 使用哈希集合存储字符的出现情况
	// rune类型可以表示任意Unicode字符，并能存储一个32位的Unicode字符编码
	// byte和rune可以直接转换
	// 用map会比数组慢,毕竟要计算
	set := make(map[byte]bool)

	left := 0
	right := 0
	maxLength := 0

	for right < n {
		// 如果当前字符已经在集合中存在，则移动左指针，并将该字符从集合中移除
		if set[s[right]] {
			delete(set, s[left])
			left++
		} else {
			// 如果当前字符不在集合中，则将其加入集合，并更新最大长度
			set[s[right]] = true
			maxLength = max_2(maxLength, right-left+1)
			right++
		}
	}

	return maxLength
}

func max_2(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func lengthOfLongestSubstring_3(s string) int {
	n := len(s)
	if n <= 1 {
		return n
	}

	cnt := [128]int{} // 用于记录字符的出现次数，数组长度为128可以覆盖ASCII字符范围
	left := 0         // 左指针，表示窗口的起始位置
	right := 0        // 右指针，表示窗口的结束位置
	maxLength := 0    // 最长不含重复字符的子串的长度

	for right < n {
		cnt[s[right]]++         // 右指针所指的字符出现次数加一
		for cnt[s[right]] > 1 { // 当右指针所指的字符出现次数大于1时，说明窗口中存在重复字符
			cnt[s[left]]-- // 移动左指针，将窗口左侧字符出现次数减一
			left++         // 左指针右移
		}
		maxLength = max_3(maxLength, right-left+1) // 更新最长不含重复字符的子串的长度
		right++                                    // 右指针右移
	}

	return maxLength
}

func max_3(a, b int) int {
	if a > b {
		return a
	}
	return b
}
